from collections import defaultdict


class Trie:
    def __init__(self):
        self.nodes = {}
        self.is_word = False

    def insert(self, word):
        if not word:
            self.is_word = True
        else:
            if word[0] not in self.nodes:
                self.nodes[word[0]] = Trie()
            self.nodes[word[0]].insert(word[1:])

    def search(self, word):
        if not word:
            return self.is_word
        if word[0] == ".":
            return any(node.search(word[1:]) for node in self.nodes.values())
        if word[0] not in self.nodes:
            return False
        return self.nodes[word[0]].search(word[1:])

    def starts_with(self, word):
        if not word:
            return True
        elif word[0] not in self.nodes:
            return False
        else:
            return self.nodes[word[0]].starts_with(word[1:])


trie = Trie()
trie.insert("bad")
trie.insert("mad")
print(trie.search("pad"))
print(trie.search("bad"))
print(trie.search(".ad"))
print(trie.search("b.."))
